﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SequenceAssembler
{
    class BubbleRemover
    {
        public BackGraph bg { get; private set; }
        private uint m_maxLength = 200;
        private double m_cutOff = 0.3;
        public BubbleRemover(BackGraph backGraph)
        {
            bg = backGraph;
        }

        public void Remove()
        {

        }

        private void TourBus()
        {
            foreach (long id in bg.CellList)
            {
                SequenceCell sc = bg.LoadCell<SequenceCell>(id);
                if (sc != null && sc.Distance == -1 && IsStartNode(sc))
                {
                    TourBusNode(sc);
                }
            }
        }

        private void TourBusNode(SequenceCell sc)
        {
            sc.Distance = 0;
            sc.Parent = sc.Id;
            Queue<SequenceCell> que = new Queue<SequenceCell>();
            que.Enqueue(sc);
            while (que.Count != 0)
            {
                SequenceCell parent = que.Dequeue();
                foreach (Arc arc in parent.Arcs)
                {
                    if (parent.Id != arc.Destination)
                    {
                        SequenceCell child = bg.LoadCell<SequenceCell>(arc.Destination);
                        if (child == null)
                        {
                            continue;
                        }
                        SequenceCell oldPrevious = bg.LoadCell<SequenceCell>(child.Parent);
                        double childDistance = parent.Distance + parent.Size / (double)arc.Multiplicity;
                        if (child.Distance == -1)
                        {
                            child.Distance = childDistance;
                            child.Parent = parent.Id;
                            bg.SaveCell(child);
                        }
                        else if (child.Distance >= childDistance)
                        {
                            child.Distance = childDistance;
                            child.Parent = parent.Id;
                            bg.SaveCell(child);
                            if (IsPrevious(parent, child) == false)
                            {
                                ComparePaths(child, oldPrevious);
                            }
                        }
                        else
                        {
                            if(IsPrevious(child, oldPrevious) == false)
                            {
                                ComparePaths(child, parent);
                            }
                        }
                    }
                }
            }
        }

        private bool IsPrevious(SequenceCell cell, SequenceCell previousCell)
        {
            while (true)
            {
                if (cell.Id == previousCell.Id)
                {
                    return true;
                }
                if (cell.Id == cell.Parent)
                {
                    return false;
                }
                cell = bg.LoadCell<SequenceCell>(cell.Parent);
            }
        }
        private bool IsStartNode(SequenceCell sc)
        {
            long twinID = bg.TwinId(sc.Id);
            SequenceCell twinCell = bg.LoadCell<SequenceCell>(twinID);
            if (twinCell.Arcs.Count == 0)
            {
                return true;
            }
            return false;
        }

        private void ComparePaths(SequenceCell destination, SequenceCell origin)
        {
            uint fastLength = 0;
            uint slowLength = 0;
            SequenceCell fastNode = destination;
            SequenceCell slowNode = origin;
            while (fastNode != slowNode)
            {
                if (fastNode.Distance < slowNode.Distance)
                {
                    fastLength += 1;
                    fastNode = bg.LoadCell<SequenceCell>(fastNode.Parent);
                }
                else if (fastNode.Distance > slowNode.Distance)
                {
                    slowLength += 1;
                    slowNode = bg.LoadCell<SequenceCell>(slowNode.Parent);
                }
                else if (IsPrevious(slowNode, fastNode) == true)
                {
                    while (slowNode != fastNode)
                    {
                        slowLength += 1;
                        slowNode = bg.LoadCell<SequenceCell>(slowNode.Parent);
                    }
                }
                else if (IsPrevious(fastNode, slowNode) == true)
                {
                    while (fastNode != slowNode)
                    {
                        fastLength += 1;
                        fastNode = bg.LoadCell<SequenceCell>(fastNode.Parent);
                    }
                }
                else
                {
                    fastLength += 1;
                    slowLength += 1;
                    fastNode = bg.LoadCell<SequenceCell>(fastNode.Parent);
                    slowNode = bg.LoadCell<SequenceCell>(slowNode.Parent);
                }
                if (slowLength > m_maxLength || fastLength > m_maxLength)
                {
                    return;
                }
            }
            string fastSequence = "";
            string slowSequence = "";
            fastSequence = BaseOperation.bitDequeToString(destination.Data);
            slowSequence = BaseOperation.bitDequeToString(destination.Data);
            SequenceCell fastStart = bg.LoadCell<SequenceCell>(destination.Parent);
            SequenceCell slowStart = bg.LoadCell<SequenceCell>(origin.Parent);
            fastSequence = ExtractSequence(fastSequence, fastStart, fastLength - 1);
            slowSequence = ExtractSequence(slowSequence, slowStart, slowLength - 1);
            if (CompareSequences(fastSequence, slowSequence) == true)
            {
                CleanRedundancy();
            }
        }

        private string ExtractSequence(string start, SequenceCell sc, uint len)
        {
            for (int i = 0; i < len; ++i)
            {
                string cur = BaseOperation.bitDequeToString(sc.Data);
                start = cur.Substring(0, cur.Length - (bg.KmerLen - 1)) + start;
                sc = bg.LoadCell<SequenceCell>(sc.Parent);
            }
            return start;
        }

        private bool CompareSequences(string fastSequence, string slowSequence)
        {
            int[][] m = new int[fastSequence.Length + 1][];
            for(int i = 0; i < m.Length; ++i)
            {
                m[i] = new int[slowSequence.Length + 1];
            }
            for (int i = 0; i <= fastSequence.Length; ++i)
            {
                m[i][0] = 0;
            }
            for (int j = 0; j <= slowSequence.Length; ++j)
            {
                m[0][j] = 0;
            }
            int avgLen = (fastSequence.Length + slowSequence.Length) / 2;
            for (int i = 1; i <= fastSequence.Length; ++i)
            {
                for (int j = 1; j <= slowSequence.Length; ++j)
                {
                    if (fastSequence[i] == slowSequence[j])
                    {
                        m[i][j] = m[i - 1][j - 1];
                    }
                    else
                    {
                        m[i][j] = Math.Max(m[i - 1][j], m[i][j - 1]);
                    }
                }
            }
            double maxScore = m[fastSequence.Length][slowSequence.Length];
            if (1 - maxScore / avgLen <= m_cutOff)
            {
                return true;
            }
            return false;
        }

        private void CleanRedundancy()
        {

        }
    }
}
